1. Field of the Invention
The present invention relates, in general, to data communications.
2. Description of the Related Art
A data communications network is the interconnection of two or more communicating entities (i.e., data sources and/or sinks) over one or more data links. A data communications network allows communication between multiple communicating entities over one or more data communications links.
One type of data communications network is the Synchronous Optical Network (SONET). Generally (although not always), SONETs are composed of network nodes strung together in a ring format.
A SONET has several relatively unique features which distinguishes it from other types of data communications networks. One unique feature is that an attempt is made to synchronize all data nodes in a SONET to the same clock system. However, insofar as SONET nodes are typically dispersed over a large geographic area, the clock signals received by each SONET node generally vary from each other in phase (e.g., due to different propagation delays arising from varying distances from a central clock) and/or frequency (e.g., when an attempt is made to synchronize various parts of a SONET to different clocks making up a clock system, where each clock in the system is supposedly synchronized in phase and frequency with every other clock but which in reality vary slightly due to physical variations). Consequently, it is not uncommon for the signals on the SONET node ingress and egress data links to vary slightly from each other either in phase and/or frequency. Consequently, rather than referring to such signals as truly synchronous, it is common in the art to refer to such signals as plesiochronous (i.e., generated by SONET nodes with separate network clocks which vary only slightly in phase and or frequency).
Since the signals on the ingress and egress data links of a SONET node can vary in phase and/or frequency, SONET does not merely rely on timing to ensure that data is correctly transported across nodes. Rather, SONET uses a data structures (called pointers in the SONET nomenclature) to compensate for frequency and phase variations across nodes. (In SONET, a pointer is simply an offset value that points to the byte where a SPE (synchronous payload envelope, which can be thought of as “user data” begins within a data structure known as a standard SONET frame. If relative severe timing differences exist between the ingress and egress data links of a SONET node, “positive stuffing” (e.g., inserting a byte) or negative stuffing (e.g., removing a byte) can be used at each SONET node to adjust for the phase and/or frequency delays, and the pointer adjusted accordingly to ensure that the next node receiving the SONET data structure can discern where a SPE resides.
In practice, since it is not known in advance whether or not the phase and/or frequency difference between ingress and egress data links of a SONET node is severe enough to warrant stuffing (positive or negative), it is common within the art to buffer received SPE data, and engage in positive or negative stuffing dependent upon whether the buffer is almost full or almost empty. If positive stuffing is used the pointer is incremented and if negative stuffing is used the pointer is decremented, thereby allowing correct discernment of the SPE at the next node. The foregoing is explained in brief overview in relation to FIG. 1.
With reference now to FIG. 1, shown is a partial block diagram of typical SONET node 100. Depicted are pointer interpreter 102, FIFO (first in, first out—the first data written into the buffer will be the first data read out of the buffer, which is illustrated via FIFO buffer data-out line 150 being connected directly to the FIFO buffer slot 1 and FIFO buffer data-in line 152 being connected to the first FIFO buffer slot which is empty—data-in line 152 is meant to indicate that SPE data is written to the first empty slot of the buffer; if data is read from the buffer the first empty slot of the buffer will appear closer to FIFO buffer slot 1 (e.g., data-in line 152 would appear in the figure to move up one slot toward buffer slot 1) and as data is written to the buffer the first empty slot of the buffer would appear closer to the last FIFO buffer slot 16 (e.g., data-in line 152 would appear in the figure to move down one slot toward buffer slot 1)) buffer 104, and pointer generator 106. Illustrated are high-level diagrams of standard SONET frames 108 and 110. Shown is that SONET frame 108 enters standard SONET node 100 via ingress data link 112. Depicted is that SONET frame 110 leaves standard SONET node 100 via egress data link 114.
SONET frames 108 and 110 show that each row of each SONET frame has 3 columns of overhead (data utilized to ensure that the SONET works correctly, and which is generally referred to in the art as a 3 column “transport gas,” since it represents a gap in the data being transported) and 87 columns of payload (data transmitted through the SONET by SONET users). Those skilled in the art will recognize that the size of each “column” will typically vary dependent upon the number of STS (synchronous transport signals) in use. For example, when one STS is in use (denoted in the art via the symbology “STS-1”) each column is 1 byte wide; when two STSes are in use (denoted in the art via the symbology “STS-2”), each column is two bytes wide; when 3 STSes are in use (denoted in the art via the symbology “STS-3”), each column is three bytes wide; etc. In general, the number of bytes per column is a function of the number of STSes in use “N,” where N is some positive integer; for example, for STS-48 (i.e., N=48) each column of each SONET frame would be 48 bytes wide.
For ease of understanding, the discussion from this point forward will generally describe embodiments via use of exemplary STS-1 SONET frames. However, those skilled in the art will appreciate that the discussion herein generalizes to virtually any STS-N SONET frame via multiplying the size of the data structures described herein by the number, N, of STSes in use in any particular implementation.
Referring now again to FIG. 1, notice that FIFO buffer 104 is shown as being finite in size (e.g., as having 16 slots). Hence, pointer interpreter 102 needs to be apprised as to when FIFO 104 is “almost full” so that pointer interpreter 102 does not inadvertently overwrite data in FIFO 104. If pointer interpreter 102 and pointer generator 106 find that FIFO 104 is almost full, pointer interpreter 102 and pointer generator 106 engage in appropriate action to ensure that data is not overwritten in FIFO 104 and that pointer generator 106 adjusts the pointer value sufficient to reflect the fact that at least one byte will not be written into FIFO 104 (e.g., the pointer is decremented to reflect negative stuffing).
If pointer interpreter 102 and pointer generator 106 find that FIFO 104 is almost empty, pointer interpreter 102 and pointer generator 106 engage in appropriate action to ensure that data is written into FIFO 104 sufficient such that data always exists in FIFO 104 sufficient such that a constant outflow of data can be maintained on egress line 114 and such that that pointer generator 106 adjusts the pointer value sufficient to reflect the fact that at least one extra byte will be written into FIFO 104 (e.g., the pointer is incremented to reflect the positive stuffing).
It has been discovered by the inventors named herein (the inventors), and such discovery forms part of the inventive content herein, that—irrespective of the fact that pointer interpreter 102 and pointer generator 106 view FIFO buffer 104 from the different standpoints of FIFO buffer data-in line 152 and FIFO buffer data-out line 150, respectively—pointer interpreter 102 and pointer generator 106 can achieve appropriate positive or negative stuffing using the same indicators of “almost empty” or “almost full” full buffers since both pointer interpreter 102 and pointer generator 106 are keyed to standard SONET frame formats. It has been discovered by the inventors, and such discovery forms part of the inventive content herein, that if either pointer interpreter 102 or pointer generator 106 is keyed to a non-standard SONET frame format (e.g., such as is described in copending application, entitled Method And Apparatus For A Rearrangeably Non-Blocking Switching Matrix, naming Saleh, Ali Najib; Duschatko, Douglas E.; and Quibodeaux, Lane Byron as inventors, having Ser. No. 09/477,166, filed Jan. 4, 2000 and hereby incorporated by reference in its entirety), severe difficulties arise with respect to determining the almost empty and almost full buffer conditions, which consequently give rise to difficulties in performing appropriate negative and/or positive stuffing.